#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""


class Solution:
    def minPathSum(self, grid):
        rows, cols = len(grid), len(grid[0])
        mat = self.make_matrix(rows+1, cols+1, 0)

        for row in range(1, rows+1):
            for col in range(1, cols+1):
                cur = grid[row-1][col-1]
                if row == 1:
                    # print('cur %s' % cur)
                    mat[row][col] = mat[row][col-1] + cur
                    # print('mat %s' % mat[row][col])
                elif col == 1:
                    mat[row][col] = mat[row-1][col] + cur
                else:
                    mat[row][col] = min(mat[row-1][col], mat[row][col-1]) + cur

        # print(mat)
        return mat[rows][cols]

    def make_matrix(self, rows, cols, init_v=None):
        one_row = [init_v] * cols

        mat = [list(one_row) for i in range(rows)]
        return mat


def main():
    print("start main")
    s = Solution()
    ret = s.minPathSum([
        [1,2],
        [1,2],
    ])
    print(ret)

if __name__ == "__main__":
    main()
